#include<iostream>
#include<vector>

using namespace std;
template<class T>
struct Greater //小堆
{
    bool operator()(const T& l,const T& r)
    {
        return l > r; 
    }
};
template<class T>
struct Less //大堆
{
    bool operator()(const T& l,const T& r)
    {
        return l < r; 
    }
};
namespace Mango
{
template<class T,class Container = vector<T>,class Compare = Greater<T>>
class priority_queue
{
public:
    priority_queue()
    {}
    ~priority_queue()
    {}
    void push(const T& val)
    {
        _con.push_back(val);
        AdjustUp(_con.size()-1);
    }
    void pop()
    {
        swap(_con[0],_con[_con.size()-1]);
        _con.pop_back();
        AdjustDown(0,_con.size());
    }
    T top()
    {
        return _con[0];
    }
    void AdjustDown(size_t parent,int n) // 向下调整
    {
        int child = parent*2+1;
        while(child < n)
        {
            if(child +1 < n && _cmp(_con[child],_con[child+1]))
                child+=1;
            if(_cmp(_con[parent],_con[child]))
            {
                swap(_con[parent],_con[child]);
                parent = child;
                child = parent*2+1;
            }
            else
            {
                break;
            }
        }
    }
    void AdjustUp(size_t child) //向上调整
    {
        size_t parent = (child-1)/2;
        while(child > 0)
        {
            if(_cmp(_con[parent],_con[child]))
            {
                swap(_con[child],_con[parent]);
                child = parent;
                parent = (child-1)/2;
            }
            else
            {
                break;
            }
        }
    }
    size_t size()
    {
        return _con.size();
    }
    bool empty()
    {
        return _con.empty();
    }
private:
    Container _con;
    Compare _cmp;
};
}
